package server.simple100;

import org.junit.Test;

/***
 *  112. 路径总和
 */
public class LeetCode112 {


	@Test
	public void test() {
//		TreeNode root = new TreeNode(5,
//				new TreeNode(4,
//						new TreeNode(11,
//								new TreeNode(7),
//								new TreeNode(2)),
//						null),
//				new TreeNode(8,
//						new TreeNode(13),
//						new TreeNode(4,
//								null,
//								new TreeNode(1)
//						)));
		TreeNode root = new TreeNode();
		//
		System.out.println(hasPathSum(root, 22));
	}


	public boolean hasPathSum(TreeNode root, int targetSum) {
		int maxNum = 0;
		// 0 表示默认找不到， 1 表示找到了
		int[] result = {0};
		maxDepth(root, maxNum, targetSum, result);
		return result[0] == 1;
	}


	void maxDepth(TreeNode root, int maxNum, int targetSum, int[] result) {
		if (root == null) {
			return;
		}
		maxNum = maxNum + root.val;
		if (root.left == null && root.right == null) {
			if (maxNum == targetSum) {
				//System.out.println("子节点:" + root.val);
				result[0] = 1;
			}
			return;
		}
		// 一直递归获取到每条线的最大深度的值
		maxDepth(root.left, maxNum, targetSum, result);
		maxDepth(root.right, maxNum, targetSum, result);
	}



	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}

//给定一个二叉树，找出其最小深度。
//
//		最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
//
//		说明：叶子节点是指没有子节点的节点。
//
//		 
//
//		示例 1：
//
//
//		输入：root = [3,9,20,null,null,15,7]
//		输出：2
//		示例 2：
//
//		输入：root = [2,null,3,null,4,null,5,null,6]
//		输出：5
//		 
//
//		提示：
//
//		来源：力扣（LeetCode）
//		链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
//		著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。